package sort

func Merge(left, right []int) []int {
	result := make([]int, 0, len(left) + len(right))

	for len(left) > 0 || len(right) > 0 {
		if len(left) == 0 {
			return append(result, right...)
		}
		if len(right) == 0 {
			return append(result, left...)
		}
		if left[0] <= right[0] {
			result = append(result, left[0])
			left = left[1:]
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}
	return result
}

func MergeSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}
	//if len(arr) <= 15 {
	//	InsertSortAdvance(arr)
	//	return arr
	//}

	middle := len(arr) / 2

	left := MergeSort(arr[:middle])
	right := MergeSort(arr[middle:])

	//if arr[middle-1] > arr[middle] {
		return Merge(left, right)
	//}
	//return arr
}

func Merge2(arr []int, l, mid, r int) {
	result := make([]int, r-l+1)
	for i := l; i <= r; i++ {
		result[i-l] = arr[i]
	}
	// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
	i := l
	j := mid+1
	for k := l ; k <= r; k ++ {
		if i > mid {  // 如果左半部分元素已经全部处理完毕，那么后续都是添加右边的剩下元素
			arr[k] = result[j-l]
			j++
		} else if j > r {  // 如果右半部分元素已经全部处理完毕，那么后续都是添加做边的元素
			arr[k] = result[i-l]
			i++
		} else if result[i-l] < result[j-l]  {  // 左半部分所指元素 < 右半部分所指元素
			arr[k] = result[i-l]
			i++
		} else {  // 左半部分所指元素 >= 右半部分所指元素
			arr[k] = result[j-l]
			j++
		}
	}
}
func __MergeSort2(arr []int, l, r int) {
	if r - l <= 15 {
		InsertSortAdvance(arr[l:r+1])
		return
	}
	mid := (l+r) / 2

	__MergeSort2(arr, l, mid)
	__MergeSort2(arr, mid+1, r)

	if arr[mid] > arr[mid+1] {
		Merge2(arr, l, mid, r)
	}
}

func MergeSort2(arr []int) {
	n := len(arr)
	__MergeSort2(arr, 0, n-1)
}
